// https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int begin = 0;
        int end = nums.size() - 1;
        vector<int> ret;

        while (begin < end)
        {
            int sum = nums[begin] + nums[end];
            if (sum > target)
            {
                --end;
            }
            else if (sum < target)
            {
                ++begin;
            }
            else
            {
                return { nums[begin], nums[end] };
            }
        }

        return ret;
    }
};